import java.util.*;

public class HashBuck {
    class Node{
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] array;
    public int usedSize;
    public static final double LOAD_Hash = 0.75;

    public HashBuck() {
        this.array = new Node[10];
    }

    public void put(int key, int val){
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null){
            if (cur.key == key){
                cur.val = val;
                break;
            }
            cur = cur.next;
        }
        Node node = new Node(key, val);
        node.next = array[index];
        array[index] = node;
        usedSize++;
        if (calculateLoad() >= LOAD_Hash){
            resize();
        }
    }

    //扩容加重写哈希

    public void resize(){
        Node[] newArray = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++){
            Node cur = array[i];
            while (cur != null){
                int index = cur.key % newArray.length;//新的存放地下标
                Node newCur = cur.next;
                cur.next = newArray[index];
                newArray[index] = cur;
                cur = newCur;
            }
        }
        array = newArray;
    }

    public double calculateLoad(){
        return usedSize * 1.0 / array.length;
    }

    //获取值
    public int get(int key){
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null){
            if (cur.key == key){
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

    //去重
    public void fun(int[] array){
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++){
            set.add(array[i]);//Set本身就可以去重
        }
        System.out.println(set);
    }

    //找到第一个重复的
    public void fun1(int[] array){
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++){
            if (!set.contains(array[i])){
                set.add(array[i]);
            }
            else {
                System.out.println(array[i]);
                return;
            }
        }
    }

    //统计重复数据出现的次数
    public void fun2(int[] array){
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++){
            if (map.get(array[i]) == null){
                map.put(array[i], 1);
            }
            else {
                int val = map.get(array[i]);
                map.put(array[i], val + 1);
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue() > 1){
                System.out.println("key :" + entry.getKey()+ "val :" + entry.getValue());
            }
        }
    }

    //只出现一次的数字
    public int singleNumber(int[] array){
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            if (!set.contains(array[i])){
                set.add(array[i]);
            }
            else {
                set.remove(array[i]);
            }
        }
        for (int i = 0; i < array.length; i++) {
            if (set.contains(array[i])){
                return array[i];
            }
        }
        return -1;
    }

    //宝石与石头
    public int findJewels(String jewels, String stones){
        int count = 0;
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            char ch = jewels.charAt(i);
            set.add(ch);
        }
        for (int i = 0; i < stones.length(); i++) {
            char ch = stones.charAt(i);
            if (set.contains(ch)){
                count++;
            }
        }
        return count;
    }

    //坏键盘打字
    public void func(String str1, String str2){
        Set<Character> set = new HashSet<>();
        for (char ch : str2.toUpperCase().toCharArray()) {
            set.add(ch);
        }
        Set<Character> setBreak = new HashSet<>();
        for (char ch : str1.toUpperCase().toCharArray()) {
            if (!set.contains(ch) && !setBreak.contains(ch)){
                setBreak.add(ch);
                System.out.print(ch);
            }
        }
    }

    //前K个单词出现频率
    public List<String> topKFrequent(String[] words, int k){
        //1.先获取单词出现次数
        Map<String, Integer> hashMap = new HashMap<>();
        for (String x : words) {
            if (hashMap.get(x) == null){
                hashMap.put(x, 1);
            }
            else {
                hashMap.put(x, hashMap.get(x) + 1);
            }
        }
        //2.建立小根堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(
                k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        }
        );
        //3.把数据放入小根堆
        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            if (minHeap.size() < k){
                minHeap.offer(entry);
            }
            else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue().compareTo(entry.getValue()) < 0){
                    minHeap.poll();
                    minHeap.add(entry);
                }
                else{
                    if (top.getValue().compareTo(entry.getValue()) == 0){
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.add(entry);
                        }
                    }
                }
            }
        }
        //4.小根堆中存好了结果
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String n = minHeap.poll().getKey();
            ret.add(n);
        }
        //翻转
        Collections.reverse(ret);
        return ret;
    }
}





















